Heap Operations: Validation & Extraction

Maintaining the Heap Property: The Sift Operations

The core of efficient heap management relies on the Heapify process, which restores the structural integrity after modification (insertion or extraction).

1. Sift Down (Key to Extraction)

When an element violates the Max-Heap property (it is smaller than its children), we use Sift Down (or sink) to push it to its correct position:

1. Compare the current node ($P$) with its largest child ($C_{max}$).
2. If $P < C_{max}$, swap $P$ and $C_{max}$.
3. Repeat the process recursively on the new position of $P$.

This process moves the violation down the tree until the property is satisfied or the element reaches a leaf node.

2. Sift Up (Key to Insertion)

When a new element is added to the end of the array (leaf node), Sift Up (or bubble) compares it with its parent and swaps upward until the Max-Heap property is restored.

Key Operation: Extract Max ($O(\log N)$)

The Extract Max operation is fundamental for Priority Queue implementation, always retrieving the highest priority item (the root) and ensuring the heap property is immediately restored.

Steps for Extraction:

1. Swap: Swap the root (`Heap[0]`, the Max element) with the last element (`Heap[N-1]`).
2. Remove: Decrease the effective size of the heap by 1 (removing the original Max value).
3. Restore: Execute the $O(\log N)$ `Sift Down` operation starting at the new `Heap[0]` to move the misplaced element down to its correct, ordered position.

Time Complexity of Heap Operations (Max-Heap)

Operation	Description	Time Complexity	Notes
Peek (Find Max)	Look at the root element.	$O(1)$	Direct array access.
Insert	Add element, then Sift Up.	$O(\log N)$	Height of the tree determines swaps.
Extract Max	Swap, remove, then Sift Down.	$O(\log N)$	Dominated by the Sift Down operation.
Build Heap	Heapify an entire array in place.	$O(N)$	Efficient linear time creation.